Most video encoding formats, including the H.264/AVC standard, entail the prediction of motion vectors within a certain search region based on block matching.
FIG. 1 and FIG. 2 illustrate the concept of a typical method of motion vector prediction according to the related art.
First, referring to FIG. 1, suppose that the target block for which motion vector prediction is to be performed is block E, and that block A, block B, and block C are blocks (i.e. previous target blocks) for which motion vector prediction was performed prior to block E. Then, the origin of the search region for the motion vector prediction for block E may be defined as the predictive motion vector (PMV), expressed as Equation 1 shown below.PMV(i)=median(MVA(i),MVB(i),MVC(i)) for i=x,y  [Equation 1]
Here, median(.) represents a function outputting a median of the input values, MVA(i), MVB(i), and MVA(i) represent the motion vectors predicted for block A, block B, and block C, respectively, x represents the horizontal component of a vector, and y represents the vertical component of a vector.
Thus, the origin of a search region may be chosen for the horizontal direction and the vertical direction, and the prediction of a motion vector for a target block may be performed within the search region. Also, the search region may be centered at the PMV, and the widths may be determined by a range value (ω) for the search region that is set beforehand for the horizontal direction and vertical direction.
FIG. 2 illustrates an example of a search region for a motion vector set that is for a target block. The search region can be expressed as Equation 2 shown below.−ω≤dx≤ω−ω≤dy≤ω  [Equation 2]
Here, dx represents the search region in the horizontal direction, and dy represents the search region in the vertical direction. Thus, the preset range value (ω) may be a half of the width of the search region (i.e. a half-width value) in the horizontal direction and vertical direction.
The prediction of the motion vector for a target block having the (U, V)-th MN size in a search region set as in FIG. 2 and Equation 2 can be performed by using the position at which the sum of absolute differences (SAD), defined as in Equation 3 shown below, is the smallest.
                                          SAD                          dx              ,              dy                                =                                    ∑                              j                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          ∑                                  i                  =                  0                                                  M                  -                  1                                            ⁢                                                          ⁢                                                                                    C                    ⁡                                          (                                              k                        ·                        l                                            )                                                        -                                      R                    ⁡                                          (                                                                        k                          +                          m                                                ,                                                  l                          +                          n                                                                    )                                                                                                                          ⁢                                  ⁢                              k            =                                          U                ×                M                            +              i                                ,                                          ⁢                      l            =                                          V                ×                N                            +              j                                      ⁢                                  ⁢                              m            =                          dx              +                              PMV                ⁡                                  (                  x                  )                                                              ,                                          ⁢                      n            =                          dy              +                              PMV                ⁡                                  (                  y                  )                                                                                        [                  Equation          ⁢                                          ⁢          3                ]            
Here, C and R represent the current image and a reference image for the prediction of the motion vector.
In this case, the motion vector difference (MVD), expressed as in Equation 4 shown below, may be calculated by using the (dx, dy) that yields the smallest SAD in the search region, and this MVD may be transmitted as a result of the motion vector prediction.MVD(i)=MV(i)−PMV(i) for i=x,y  [Equation 4]
Here, MV(i) represents the motion vector predicted for the target block.
However, the method of motion vector prediction based on the related art as described above requires a large amount of computation, and thus its application to various services may be limited.